#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int violentMatch(const char* s, const char* p)
{
  if (s == NULL || p == NULL) {
    return -1;
  }

  unsigned int sLen = strlen(s);
  unsigned int pLen = strlen(p);

  unsigned int i = 0, j = 0;
  while (i != sLen && j != pLen) {
    if (s[i] == p[j]) {
      ++i;
      ++j;
      continue;
    }

    i = i - j + 1;
    j = 0;
  }
  if (j == pLen) {
    return i - j;
  }

  return -1;
}

int getNext(int *next, const char* p, int len)
{
  if (next == NULL || p == NULL || len <= 0) {
    return -1;
  }
  next[0] = -1;

  int k = -1;
  int i = 0;
  while (i < len - 1) {
    if (k == -1 || p[i] == p[k]) {
      ++k;
      ++i;
      if (p[i] != p[k])
        next[i] = k;
      else
        next[i] = next[k];
    } else {
      k = next[k];
    }
  }

  return 0;
}

int KMP(const char* s, const char* p)
{
  if (s == NULL || p == NULL) {
    return -1;
  }

  int sLen = strlen(s);
  int pLen = strlen(p);
  if (sLen == 0 || pLen == 0) {
    return -1;
  }

  int* next = (int*)malloc(pLen * sizeof(int));
  if (next == NULL) {
    return -1;
  }
  int ret = getNext(next, p, pLen);
  if (ret != 0) {
    free(next);
    return ret;
  }

  int i = 0, j = 0;
  while (i < sLen && j < pLen) {
    if (j == -1 || s[i] == p[j]) {
      ++i;
      ++j;
    } else {
      j = next[j];
    }
  }
  free(next);

  if (j == pLen) {
    return i - j;
  }
  return -1;
}

int main(int argc, char* argv[])
{
  char* s = "BBC ABCDAB ABCDABCDABDE";
  char* p = "ABCDABD";
  char* m = "ABABAAABA";
  printf("Get violent match posotion: %d\n", violentMatch(s, p));
  printf("Get KMP match posotion: %d\n", KMP(s, p));
  printf("Get KMP match posotion: %d\n", KMP(s, m));
  return 0;
}

